package com.LeetCode.dp;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 打家劫舍
 */
public class StolenMoney {

    /**
     * 最普通的小区
     */
    public int rob1(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        if(len == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i<len; i++){
            dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[len-1];
    }

    /**
     * 环形小区
     */
    public int rob2(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        if(len == 2) return Math.max(nums[0], nums[1]);

        int[] tmp1 = new int[len-1];// 0 ~ n - 1
        int[] tmp2 = new int[len-1];// 1 ~ n
        System.arraycopy(nums,0,tmp1,0, tmp1.length);
        System.arraycopy(nums,1,tmp2,0, tmp2.length);

        int res = 0;

        int[] dp = new int[len-1];
        dp[0] = tmp1[0];
        dp[1] = Math.max(tmp1[0] , tmp1[1]);
        for(int i = 2; i<len-1; i++){
            dp[i] = Math.max(dp[i-2] + tmp1[i], dp[i-1]);
        }

        res = Math.max(res , dp[len-2]);

        Arrays.fill(dp,0);
        dp[0] = tmp2[0];
        dp[1] = Math.max(tmp2[0] , tmp2[1]);
        for(int i = 2; i<len-1; i++){
            dp[i] = Math.max(dp[i-2] + tmp2[i], dp[i-1]);
        }

        res = Math.max(res , dp[len-2]);

        return res;
    }

    HashMap<TreeNode, Integer> mono = new HashMap<>();

    /**
     * 小区变成了二叉树
     * 采用递归 + 记忆化搜索求解
     */
    public int rob(TreeNode root){
        if(root == null)
            return 0;

        if(mono.containsKey(root))
            return mono.get(root);

        int stole_it = root.val
                + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
                + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));

        int not_stole_it = rob(root.left) + rob(root.right);

        int res = Math.max(stole_it , not_stole_it);

        mono.put(root,res);

        return res;
    }

    @Test
    public void test(){
        int[] arr = {1,2,3,1};
        System.out.println(rob2(arr));
    }
}
